package com.origin.niuke.array;

import java.util.Arrays;

/**
 * 下一个排列
 * 算法：数组 + 找规律
 * 从排第一位的数组开始, [1, 2, 3, 4]
 * 1、先交换最后两位 [1, 2, 4, 3]
 * 2、然后再把前一位加入交换中, 也就是把 2 拉进去, 将 2 和 3 交换, 再把最后两位排序 [1, 3, 2, 4]
 * 3、重复 1 和 2
 * 从后往前, 找到一个递减序列, 比如递减序列为 [i, n - 1], 右闭区间的值永远是 n - 1, 将 i 的前一位 i - 1 拉进来排列
 *
 * @author yezh
 * @date 2023/2/9 21:40
 */
public class NC194 {

    public int[] nextPermutation (int[] nums) {
        int n = nums.length, i = n - 2, j = n - 1;
        if (n == 0 || n == 1) return nums;
        while (i > 0 && nums[i] >= nums[i + 1]) i--;
        // i = 0 表示已经将 nums[n - 1] 移到开头了
        if (i == 0) {
            Arrays.sort(nums);
            return nums;
        }
        // 找到第一个比 nums[i] 大的数
        while (j > 0 && nums[j] <= nums[i]) j--;
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        Arrays.sort(nums, i + 1, n);
        return nums;
    }

}
